package chart.shortest_path;

import chart.图的存储.AbstractGraph;
import chart.图的存储.AdjacencyTable;
import chart.图的存储.Edge;

import java.util.Arrays;

/**
 * 适用于带权图, 因为 DFS 可以回溯
 *
 * @author yezh
 * @date 2024/9/14 14:03
 */
public class DFS {

    public static void main(String[] args) {
        // 时间复杂度: O(V + E), 需要遍历顶点和边
        AbstractGraph graph = new AdjacencyTable(6, false);
        graph.createGraph(Edge.graphDFS());
        System.out.println(Arrays.toString(getDistance(0, graph)));
    }

    public static int[] getDistance(int vertex, AbstractGraph graph) {
        // 顶点个数
        int n = graph.getV();
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        dfs(0, 0, distance, graph);
        return distance;
    }

    private static void dfs(int vertex, int dist, int[] distance, AbstractGraph graph) {
        // 剪枝, vertex 可能已经遍历过了或者有另外更好的路径
        if (dist >= distance[vertex]) return;
        distance[vertex] = dist;
        for (Edge edge : graph.getNeighborEdge(vertex))
            dfs(edge.getArcHead(), dist + edge.getWeigh(), distance, graph);
    }

}
